Tính xác định

Khả năng nhận dạng

Với một ôtômat dưới lên, một số hạng nền t {\displaystyle t} (nghĩa là một cây) được đoán nhận nếu có một phép biến đổi bắt đầu từ t và kết thúc bởi q(t). Ngược lại, với ôtômat trên xuống, một số hạng nền t {\displaystyle t} được đoán nhận nếu có một phép biến đổi bắt đầu từ q(t) và kết thúc bằng t, với q(t) là một trạng thái bắt đầu.

Ngôn ngữ cây L ( A ) {\displaystyle L(A)} được đoán nhận bởi ôtômat cây A {\displaystyle A} là tập hợp tất cả số hạng nền được đoán nhạn bởi A {\displaystyle A} . Một tập các số hạng nền có thể được đoán nhận nếu tồn tại một ôtômat cây đoán nhận nó.

Một thuộc tính quan trọng là biến đổi đồng hình tuyến tính (nghĩa là bảo tồn bậc) không thay đổi tính đoán nhận được.

Tính đầy đủ và giản lược

Một ôtômat cây hữu hạn không xác định là đầy đủ nếu có ít nhất một luật chuyển cho mỗi cặp ký hiệu-trạng thái. Một trạng thái q {\displaystyle q} là đến được nếu có một số hạng nền (ground term) t {\displaystyle t} sao cho có một phép biến đổi từ t {\displaystyle t} đến q ( t ) {\displaystyle q(t)} . Một ôtômat cây hữu hạn là giản lược nếu mọi trạng thái của nó đều đến được.

Định lý bơm

Bao đóng

Lớp các ngôn ngữ cây có thể nhận dạng được là đóng với các phép hợp, bù và giao.

Định lý Myhill-Nerode